package com.sourcetrip.algorithm.sort.radix;

import com.sourcetrip.algorithm.abs.AbstractCustomedObjectSort;
import com.sourcetrip.utils.Integers;

/**
 * @author: ZhouBert
 * @date: 2021/1/4
 * @description: 十大排序算法之九：基数排序（的对象比较版本，并不能比较自定义对象） --
 * 算法针对整型进行排序，依次对整型的低位到高位进行 Counting Sort!
 * (高位相比低位权重更高，在保证稳定性的前提下，权重更高的需放到越后面来进行比较！)
 */
public class RadixCustomedSortV0 extends AbstractCustomedObjectSort<Integer> {

    //region    constructor

    public RadixCustomedSortV0(int k) {
        this.k = k;
    }


    //endregion

    /**
     * K 进制
     */
    private int k;

    /**
     * 作为基数排序的框架方法
     *
     * @param objectArr 待排序的数组
     */
    @Override
    protected void sortArr(Integer[] objectArr) {

        //boolean finished = false;
        int index = 0;
        //pre 遍历一遍，找到最大的数，然后得到 maxIndex:循环的次数
        int max = objectArr[0];
        for (int i = 1; i < objectArr.length; i++) {
            max = Math.max(max, i);
        }
        //求出 max
        int maxIndex = getMaxIndex(max);


        while (maxIndex-- > 0) {
            int[] record = new int[k];

            //1.构建记录数组
            for (int i = 0; i < objectArr.length; i++) {
                record[getRemainder(objectArr[i], index)]++;
            }

            //2.重构 record array
            for (int i = 1; i < record.length; i++) {
                record[i] = record[i - 1] + record[i];
            }

            //3.根据规则填入
            Integer[] newArr = new Integer[objectArr.length];
            for (int i = objectArr.length - 1; i >= 0; i--) {
                newArr[--record[getRemainder(objectArr[i], index)]] = objectArr[i];
            }

            //objectArr = newArr;
            for (int i = 0; i < newArr.length; i++) {
                objectArr[i] = newArr[i];
            }

            index++;
        }


    }


    //region	utils methods

    /**
     * 获取最大的 去位 操作
     *
     * @param max
     * @return
     */
    protected int getMaxIndex(int max) {
        int res = 1;
        while ((max=(max / k)) > 0) {
            res++;
        }
        return res;
    }


    /**
     * 获取元素的第 index 层的余数
     *
     * @param item
     * @param index
     * @return
     */
    protected int getRemainder(Integer item, int index) {
        int res = item;
        while (index-- > 0) {
            res = res / k;
        }
        return res % k;
    }


    //endregion


    /**
     * 比 Octal 差了些，6s
     * @param args
     */
    public static void main(String[] args) {
        RadixCustomedSortV0 sortV0 = new RadixCustomedSortV0(10);
        Integer[] random = Integers.random(10_000, 10, 100_000);
        //random = new Integer[]{5, 4, 3, 2, 1};
        random = Integers.random(10_000_000, 10, 100_000_000);
        sortV0.sort(random);
        System.out.println(sortV0);
        System.out.println(Integers.isAscOrder(random));
        //System.out.println(Arrays.toString(random));
    }
}
